#ifndef __QUEEN_H__
#define __QUEEN_H__
#include <iostream>
using namespace std;

// 回溯求解n皇后问题
void BackTrack(int c, int n, bool row[], bool diag[], bool backDiag[], int x[]);

// 输出一组解
void OutSolution(int n, int x[]);

void Queen(int n)
// 求解n皇后问题
{
    bool *row = new bool[n + 1];      // 行是否有皇后
    bool *diag = new bool[2 * n];     // 主对角线是否有皇后
    bool *backDiag = new bool[2 * n]; // 反对角线是否有皇后
    int *x = new int[n + 1];          // 临时变量

    // 初值
    for (int i = 1; i <= n; i++)
        row[i] = false;
    for (int i = 1; i < 2 * n; i++)
        diag[i] = false, backDiag[i] = false;

    BackTrack(1, n, row, diag, backDiag, x); // 递归求解

    // 释放空间
    delete[] row;
    delete[] diag;
    delete[] backDiag;
    delete[] x;
}

void BackTrack(int c, int n, bool row[], bool diag[], bool backDiag[], int x[])
// 操作结果：前i-1个皇后已经放置后，，为第i个皇后选择合适的位置
{
    int r;
    if (c > n)
    {
        // c>n 表示 1~n 个皇后已放置好
        OutSolution(n, x); // 得到解就输出解
    }
    else
    {
        for (r = 1; r <= n; r++)
        { // 第 c 个皇后所放置的行
            if (!row[r] && !diag[n - c + r] && !backDiag[r + c - 1])
            {                                                           // 位置（r, c）所在的行，对角线没放置皇后，则在（r, c）放置的第 c 个皇后
                row[r] = diag[n - c + r] = backDiag[r + c - 1] = true;  // （r, c）已有皇后
                x[c] = r;                                               // 表示第 c 个皇后所放置的行
                BackTrack(c + 1, n, row, diag, backDiag, x);            // 试探第 c+1 个皇后所放置的位置
                row[r] = diag[n - c + r] = backDiag[r + c - 1] = false; // 释放（r, c），进行回溯
            }
        }
    }
}

void OutSolution(int n, int x[])
// 输出皇后问题的解
{
    int static num = 0; // num表示已求得的解的个数
    cout << "第" << ++num << "个解：";
    for (int c = 1; c <= n; c++)
    { // 输出解
        cout << "(" << x[c] << "," << c << ") ";
    }
    cout << '\n';
}

#endif